/**
 * @file cd_list.c
 * @brief 通用链表实现文件
 * @details 提供高效、线程安全的双向链表操作实现
 *          支持FIFO队列、栈操作、遍历等多种数据结构需求
 *          适用于嵌入式系统和实时应用
 * 
 * @author 修改团队：mastwet@Undefine Innovation
 * @date 2024
 * @copyright MIT License
 * 
 * @note 基于Linux内核链表设计思想，使用侵入式链表结构
 * @note 所有操作均为O(1)时间复杂度，除list_count()为O(n)
 * @note 线程安全性由调用者保证
 */

#include "cd_list.h"

/**
 * @brief 初始化链表头
 * @param head 链表头指针
 * @details 创建一个空的双向循环链表
 *          头节点的next和prev都指向自身，表示链表为空
 * 
 * @note 必须在链表使用前调用此函数初始化
 * @note 时间复杂度：O(1)
 */
void list_init(list_head_t *head)
{
    head->next = head;
    head->prev = head;
}

/**
 * @brief 在指定位置插入新节点
 * @param new 要插入的新节点
 * @param prev 前一个节点
 * @param next 后一个节点
 * @details 在prev和next之间插入新节点
 *          执行双向链表的标准插入操作
 * 
 * @note 不检查参数有效性，由调用者保证
 * @note 时间复杂度：O(1)
 */
void list_add(list_head_t *new, list_head_t *prev, list_head_t *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}

/**
 * @brief 在链表头部插入节点
 * @param new 要插入的新节点
 * @param head 链表头
 * @details 将新节点插入到链表头部（头节点之后）
 *          适用于栈的push操作
 * 
 * @note 时间复杂度：O(1)
 */
void list_add_head(list_head_t *new, list_head_t *head)
{
    list_add(new, head, head->next);
}

/**
 * @brief 在链表尾部插入节点
 * @param new 要插入的新节点
 * @param head 链表头
 * @details 将新节点插入到链表尾部（头节点之前）
 *          适用于队列的enqueue操作
 * 
 * @note 时间复杂度：O(1)
 */
void list_add_tail(list_head_t *new, list_head_t *head)
{
    list_add(new, head->prev, head);
}

/**
 * @brief 删除指定位置的节点
 * @param prev 前一个节点
 * @param next 后一个节点
 * @details 从链表中移除prev和next之间的节点
 *          仅修改指针，不释放内存
 * 
 * @note 不检查参数有效性，由调用者保证
 * @note 时间复杂度：O(1)
 */
void list_del(list_head_t *prev, list_head_t *next)
{
    next->prev = prev;
    prev->next = next;
}

/**
 * @brief 从链表中移除指定节点
 * @param entry 要移除的节点
 * @details 从链表中移除指定节点，并将其重新初始化为空节点
 *          不释放节点内存，仅断开链表连接
 * 
 * @note 被移除的节点可以安全地重新使用
 * @note 时间复杂度：O(1)
 */
void list_remove(list_head_t *entry)
{
    list_del(entry->prev, entry->next);
    list_init(entry);
}

/**
 * @brief 检查链表是否为空
 * @param head 链表头
 * @return 如果链表为空返回1，否则返回0
 * @details 通过检查头节点的next指针是否指向自身来判断链表是否为空
 * 
 * @note 时间复杂度：O(1)
 */
int list_empty(const list_head_t *head)
{
    return head->next == head;
}

/**
 * @brief 从链表头部获取并移除节点
 * @param head 链表头
 * @return 成功时返回链表头部的节点指针，链表为空时返回NULL
 * @details FIFO队列的dequeue操作实现
 *          从链表头部获取节点并从链表中移除
 * 
 * @note 调用者负责检查返回值是否为NULL
 * @note 时间复杂度：O(1)
 */
void *list_get(const list_head_t *head)
{
    list_head_t *pos = head->next;
    if (pos == head)
        return NULL;  /* 链表为空 */
    
    list_remove(pos);
    return pos;
}

/**
 * @brief 将节点添加到链表尾部
 * @param new 要添加的新节点
 * @param head 链表头
 * @details FIFO队列的enqueue操作实现
 *          将新节点添加到链表尾部
 * 
 * @note 等价于list_add_tail()
 * @note 时间复杂度：O(1)
 */
void list_put(list_head_t *new, list_head_t *head)
{
    list_add_tail(new, head);
}

/**
 * @brief 查看链表头部节点但不移除
 * @param head 链表头
 * @return 成功时返回链表头部的节点指针，链表为空时返回NULL
 * @details 查看链表头部节点但不修改链表结构
 *          适用于检查队列头部元素
 * 
 * @note 不修改链表结构，仅查看
 * @note 时间复杂度：O(1)
 */
void *list_peek(const list_head_t *head)
{
    list_head_t *pos = head->next;
    if (pos == head)
        return NULL;  /* 链表为空 */
    
    return pos;
}

/**
 * @brief 从链表尾部获取并移除节点
 * @param head 链表头
 * @return 成功时返回链表尾部的节点指针，链表为空时返回NULL
 * @details 栈的pop操作实现
 *          从链表尾部获取节点并从链表中移除
 * 
 * @note 调用者负责检查返回值是否为NULL
 * @note 时间复杂度：O(1)
 */
void *list_pop(list_head_t *head)
{
    list_head_t *pos = head->prev;
    if (pos == head)
        return NULL;  /* 链表为空 */
    
    list_remove(pos);
    return pos;
}

/**
 * @brief 计算链表中的节点数量
 * @param head 链表头
 * @return 链表中的节点数量
 * @details 遍历整个链表计算节点数量
 *          对于空链表返回0
 * 
 * @warning 对于长链表，此操作可能耗时较长
 * @note 时间复杂度：O(n)，n为链表长度
 */
unsigned int list_count(const list_head_t *head)
{
    unsigned int count = 0;
    list_head_t *pos;
    
    /* 遍历链表计算节点数量 */
    for (pos = head->next; pos != head; pos = pos->next)
        count++;
    
    return count;
}